#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *
 * */
//获取一个排序数组最小的交换次数 感觉有点像那个挖坑那个 这个应该也是一个很经典的题
int minSwaps(vector<int> arr, int n) {
    // Create an array of
    // pairs where first
    // element is array element
    // and second element
    // is position of first element
    pair<int, int> arrPos[n];
    for (int i = 0; i < n; i++) {
        arrPos[i].first = arr[i];
        arrPos[i].second = i;
    }

    // Sort the array by array
    // element values to
    // get right position of
    // every element as second
    // element of pair.
    sort(arrPos, arrPos + n);

    // To keep track of visited elements.
    // Initialize
    // all elements as not visited or false.
    vector<bool> vis(n, false);

    // Initialize result
    int ans = 0;

    // Traverse array elements
    for (int i = 0; i < n; i++) {
        // already swapped and corrected or
        // already present at correct pos
        if (vis[i] || arrPos[i].second == i)
            continue;
        // find out the number of  node in
        // this cycle and add in ans
        int cycle_size = 0;
        int j = i;
        while (!vis[j]) {
            vis[j] = 1;
            // move to next node
            j = arrPos[j].second;
            cycle_size++;
        }
        // Update answer by adding current cycle.
        if (cycle_size > 0) {
            ans += (cycle_size - 1);
        }
    }

    // Return result
    return ans;
}

int minSwaps(vector<int> arr) {
    vector<pair<int, int>> newArr;
    vector<bool> visi(arr.size(), false);
    //记录下标值
    for (int i = 0; i < arr.size(); ++i) {
        newArr.push_back(make_pair(arr[i], i));
    }

    //排序
    sort(newArr.begin(), newArr.end());

    int ret = 0;

    for (int i = 0; i < newArr.size(); ++i) {

        if (visi[i] || i == newArr[i].second)
            continue;

        int j = i;
        int count = 0;
        while (!visi[j] && j != newArr[j].second) {
            count++;
            visi[j] = 1;

            j = newArr[j].second;//获取原来那个位置的情况 如果原来的位置还是等于原来的数 那就跳出循环

        }

        if (count > 0)
            ret += count - 1;
    }


    return ret;

}

//获取最小公倍数

int lowestNums(vector<int> &vec) {
    unsigned lcm = 1;
    for (int i = 0; i < vec.size(); i++) {
        lcm = lcm * vec[i] / (__gcd(lcm, vec[i])); //求最小公倍数
    }

    return lcm;

}
//求最大公约数问题 但是用这个求最小公倍数出问题了 因为那边返回1 这边有盲区因为不能直接求公约然后求拱北
// 应该全部求公倍数 或者公约数  就是上面那个
//int solve(vector<int> &vec)
//{
//    if(vec.size()<=0)
//        return 0;
//    if(vec.size()==1)
//        return vec[0];
//    int first=vec[0];
//    for(int  i=1;i<vec.size();i++)
//    {
//        int num=gcb(first,vec[i]);
//        if(num==1)
//            return 1;
//        else
//            first=num;
//
//    }
//    return first;
//
//}